package demo3LinkList;

import demo3LinkList.MyNodeAndMyList.Node;
import demo3LinkList.MyNodeAndMyList.NodeList;
import org.junit.Test;

/**
 * @ClassName $ {NAME}
 * @Description TODO  找出带环单链表的交点 ;思路：先找到快慢指针的相遇点，然后在找到单链表环交点
 * @Author shenxinyuan
 * @Date $ {DATE} $ {TIME}
 * @Version 1. 0
 **/

public class QuilAndSlowPointer {


    @Test
    public void test(){
        NodeList nodeList = new NodeList<>();
        nodeList.addHead(1);
        nodeList.addHead(2);
        nodeList.addHead(3);
        nodeList.addHead(4);
        nodeList.addHead(5);
        nodeList.addHead(6);
        nodeList.addHead(7);
        //7 6   5   4   3   2   1       1指向5  寻找换的入口节点  5
        nodeList.makeCircle(2);//连成一个环
        //到此面试题中的链表已创建好

        //先找到相遇点记录下来
        Node meetPoint = null;
        meetPoint = nodeList.findMeetPoint();

        //检验相遇点
        System.out.println("meetPoint:"+meetPoint.getValue()+" ");

//       然后分别让slow回到起始点，fast回到相遇点；两者同时走相同的长度当slow到达相遇点时，
//       fast与slow再次相遇点就是环链入口
        Node entranceNode = nodeList.entranceNode(meetPoint);
        System.out.println("entranceNode:"+entranceNode.getValue());
    }
}
